package org.basis.algorithm.recursion;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 打印所有子序列
 *
 * @author Mr_wenpan@163.com 2021/12/27 22:58
 */
public class PrintAllSubsquences {

    public static void main(String[] args) {

        char[] chars = new char[]{'1', 'x', 0};
        System.out.println("chars = " + Arrays.toString(chars));

        final String str = "abc";
        printAllSubsquence(str);

    }

    /**
     * 给你一个字符串，打印他的所有子序列
     */
    public static void printAllSubsquence(String str) {
        if (str == null) {
            return;
        }

//        process(str.toCharArray(), 0, new ArrayList<>());
        process2(str.toCharArray(), 0);
    }

    /**
     * 优化后的方法，空间复杂度为O（1）
     */
    public static void process2(char[] chars, int i) {
        if (i == chars.length) {
            // 使用自定义打印
            print(chars);
            return;
        }
        // 要第i个字符
        process2(chars, i + 1);

        // 先将第i个字符暂存起来
        char temp = chars[i];
        // 第i个位置字符弄成0
        chars[i] = 0;
        // 不要第i个字符
        process2(chars, i + 1);
        // 还原
        chars[i] = temp;
    }

    /**
     * 自定义打印方法，char[i] == 0 的不打印
     */
    private static void print(char[] chars) {
        if (chars == null) {
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != 0) {
                System.out.print(chars[i]);
            }
        }
        System.out.println();
    }

    /**
     * 未优化的方法，空间复杂度O（n）
     */
    public static void process(char[] chars, int i, List<Character> res) {

        if (i == chars.length) {
            // 到达最后一个位置了，打印
            System.out.println(res.toString());
            return;
        }
        // 对于每一个位置的数都可以选择要或者不要

        // 要i位置的字符，这里需要拷贝一份，以免对下面的不要i位置的字符递归造成影响
        List<Character> copy = copy(res);
        copy.add(chars[i]);
        process(chars, i + 1, copy);

        // 不要i位置的字符
        process(chars, i + 1, res);

    }

    public static List<Character> copy(List<Character> res) {
        if (res == null) {
            return null;
        }
        if (res.size() == 0) {
            return new ArrayList<>();
        }
        return new ArrayList<>(res);
    }

}
